home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / graph.h < prev    next >
C/C++ Source or Header  |  1994-08-05  |  31KB  |  1,098 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  graph.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_GRAPH_H
  17. #define LEDA_GRAPH_H
  18.  
  19. //------------------------------------------------------------------------------
  20. //   directed graphs
  21. //   
  22. //   Redesign: November 1993
  23. //------------------------------------------------------------------------------
  24.  
  25.  
  26. #include <LEDA/basic.h>
  27. #include <LEDA/list.h>
  28. #include <LEDA/impl/olist.h>
  29.  
  30.  
  31. class node_struct;
  32. typedef node_struct* node;
  33.  
  34. class edge_struct;
  35. typedef edge_struct* edge;
  36.  
  37. class adj_link_struct1 : public obj_link {};
  38. typedef adj_link_struct1* adj_link1;
  39.  
  40. class adj_link_struct2 : public obj_link {};
  41. typedef adj_link_struct2* adj_link2;
  42.  
  43. class node_link_struct : public obj_link {};
  44. typedef node_link_struct* node_link;
  45.  
  46. class edge_link_struct : public obj_link {};
  47. typedef edge_link_struct* edge_link;
  48.  
  49. class aux_link_struct : public obj_link {};
  50. typedef aux_link_struct* aux_link;
  51.  
  52.  
  53. typedef int  (*cmp_graph_node) (const node&, const node&);
  54. typedef int  (*cmp_graph_edge) (const edge&, const edge&);
  55.  
  56.  
  57. //------------------------------------------------------------------------------
  58. // class node_struct: internal representation of nodes
  59. //------------------------------------------------------------------------------
  60.  
  61. class node_struct : public aux_link_struct,  // used for node_list
  62.                     public node_link_struct  // chaining all nodes
  63. {  
  64.  
  65.    friend class graph;
  66.    friend class ugraph;
  67.    friend class planar_map;
  68.    friend class node_stack;
  69.    friend class node_queue;
  70.    friend class node_list;
  71.    friend class b_node_pq;
  72.    //friend class node_data;
  73.    //friend class node_pq;
  74.  
  75.    
  76.    graph*    g;             // pointer to graph of node 
  77.    int       name;          // internal name (index)  
  78.    obj_list  adj_edges[2];  // lists of adjacent and incoming edges
  79.    edge      adj_iterator; //
  80.  
  81. public:
  82.  
  83.    GenPtr data[3];      // data[0]: GRAPH
  84.                         // data[1]: node_stack, node_queue, node_pq, etc.
  85.                         // data[2]: node_data
  86.  
  87.    node_struct(GenPtr i=0) 
  88.    { data[0] = i; name = -1; g = nil; adj_iterator = nil; }
  89.  
  90. LEDA_MEMORY(node_struct)
  91.  
  92. FRIEND_INLINE graph* graph_of(node);
  93. FRIEND_INLINE graph* graph_of(edge);
  94. FRIEND_INLINE int    indeg(node);
  95. FRIEND_INLINE int    outdeg(node);
  96. FRIEND_INLINE int    degree(node);
  97. FRIEND_INLINE int    index(node);
  98.  
  99. FRIEND_INLINE edge   First_Adj_Edge(node,int);
  100. FRIEND_INLINE edge   Last_Adj_Edge(node,int);
  101.  
  102. friend void init_node_data(const graph&,int,GenPtr);
  103.  
  104. };
  105.  
  106.  
  107.  
  108. //------------------------------------------------------------------------------
  109. // class edge_struct: internal representation of edges
  110. //------------------------------------------------------------------------------
  111.  
  112. class edge_struct : public adj_link_struct1,  // chaining of adjacent out-edges
  113.                     public adj_link_struct2,  // chaining of adjacent in-edges
  114.                     public edge_link_struct   // chaining of all edges
  115. { 
  116.    friend class graph;
  117.    friend class ugraph;
  118.    friend class planar_map;
  119.  
  120.    int  name;          // internal name (index)  
  121.    node s;             // source node 
  122.    node t;             // target node
  123.    edge rev;           // space for reverse edge (used by planar_map)
  124.  
  125.    GenPtr data[1];     // space for data (data[0] used by GRAPH)
  126.  
  127.    edge_struct(node v, node w, GenPtr i=0)
  128.    { data[0] = i;
  129.      name = -1;
  130.      s = v;
  131.      t = w;
  132.    }
  133.  
  134. public:
  135.  
  136. LEDA_MEMORY(edge_struct)
  137.  
  138. FRIEND_INLINE graph* graph_of(edge);
  139. FRIEND_INLINE node   source(edge);
  140. FRIEND_INLINE node   opposite(node,edge);
  141. FRIEND_INLINE node   target(edge);
  142. FRIEND_INLINE int    index(edge);
  143.  
  144. };
  145.  
  146.  
  147. inline int    outdeg(node v) { return v->adj_edges[0].length(); }
  148. inline int    indeg(node v)  { return v->adj_edges[1].length(); }
  149. inline int    degree(node v) { return indeg(v) + outdeg(v); }
  150.  
  151. inline int    index(node v)    { return v->name;    }
  152. inline graph* graph_of(node v) { return v->g; }
  153.  
  154. inline graph* graph_of(edge e) { return e->s->g;   }
  155. inline node   source(edge e)   { return e->s;      }
  156. inline node   opposite(node v, edge e) { return (v==e->s) ? e->t : e->s; }
  157.  
  158. inline node   target(edge e)   { return e->t;      }
  159. inline int    index(edge e)    { return e->name;    }
  160.  
  161.  
  162. // parameterized access of adjacent edges (portable code?)
  163. // outgoing (i=0) or incoming (i=1) edges
  164.  
  165. inline edge First_Adj_Edge(node v, int i)  
  166. { GenPtr p = v->adj_edges[i].first() - i;
  167.   return edge(p); }
  168.  
  169. inline edge Last_Adj_Edge(node v, int i)  
  170. { GenPtr p = v->adj_edges[i].last() - i;
  171.   return edge(p); }
  172.  
  173. inline edge Succ_Adj_Edge(edge e, int i) 
  174. { GenPtr p = ((obj_link*)(((obj_link*)GenPtr(e))+i))->succ_item() - i;
  175.   return edge(p); }
  176.  
  177. inline edge Pred_Adj_Edge(edge e, int i) 
  178. { GenPtr p = ((obj_link*)(((obj_link*)GenPtr(e))+i))->pred_item() - i;
  179.   return edge(p); }
  180.  
  181. inline edge Leda_Nil_Edge(int i) 
  182. { GenPtr p = (obj_link*)0 - i;
  183.   return edge(p); }
  184.  
  185.  
  186.  
  187.  
  188.  
  189. //------------------------------------------------------------------------------
  190. // graph_array<node/edge>
  191. //
  192. // base class for node and edge arrays
  193. //
  194. //------------------------------------------------------------------------------
  195.  
  196. template <class itype>
  197.  
  198. class _CLASSTYPE graph_array {
  199.  
  200. graph* g;     // array is declared for graph *g 
  201.  
  202. int mx_i;    // maximal node index in g at time of creation
  203.  
  204. protected:
  205.  
  206. GenPtr* arr;  
  207.  
  208. virtual void clear_entry(GenPtr&) const {}
  209. virtual void copy_entry(GenPtr&)  const {}
  210.  
  211. public:
  212.  
  213. virtual int cmp_entry(itype,itype) const  { return 0; }
  214.  
  215.  GenPtr& entry(itype x)
  216.  { if (g != graph_of(x) || index(x) > mx_i)
  217.           error_handler(102,"(node/edge)_array[x]: not defined for x");
  218.   return arr[index(x)];
  219.  }
  220.  
  221.  GenPtr  inf(itype x) const
  222.  { if (g != graph_of(x) || index(x) > mx_i)
  223.           error_handler(102,"(node/edge)_array[x]: not defined for x");
  224.   return arr[index(x)];
  225.  }
  226.  
  227.  GenPtr& entry(int i) { return arr[i]; }
  228.  
  229.  void init(const graph&, int, GenPtr);
  230.  void init(const graph_array<itype>&);
  231.  
  232.  void clear();
  233.  int  size() const     { return mx_i+1;}
  234.  
  235.  graph_array() { g = 0; mx_i = -1; arr = 0;}
  236.  
  237.  virtual ~graph_array() { clear(); }
  238.  
  239. };
  240.  
  241.  
  242. //------------------------------------------------------------------------------
  243. // graph: base class for all graphs
  244. //------------------------------------------------------------------------------
  245.  
  246. class graph {
  247.  
  248. friend class ugraph;
  249. friend class planar_map;
  250.  
  251. //list<node> V;              /* list of all nodes */
  252. obj_list V;
  253.  
  254. //list<edge> E;              /* list of all edges */
  255. obj_list E;
  256.  
  257. int max_n_index;      // maximal node index 
  258. int max_e_index;      // maximal edge index
  259.  
  260. bool   undirected;    // true iff graph is undirected
  261.  
  262.  
  263. /* space: 2 lists + 4 words + "virtual" = 2*20 + 5*4 bytes = 60 bytes */
  264.  
  265. virtual void init_node_entry(GenPtr& x)  { x=0; }
  266. virtual void init_edge_entry(GenPtr& x)  { x=0; }
  267.  
  268. virtual void copy_node_entry(GenPtr&) const {}
  269. virtual void copy_edge_entry(GenPtr&) const {}
  270.  
  271. virtual void clear_node_entry(GenPtr& x) const { x=0; }
  272. virtual void clear_edge_entry(GenPtr& x) const { x=0; }
  273.  
  274. virtual void read_node_entry(istream& in, GenPtr& x)  { Read(x,in); }
  275. virtual void read_edge_entry(istream& in, GenPtr& x)  { Read(x,in); }
  276.  
  277. virtual void write_node_entry(ostream& o, GenPtr& x)  const { Print(x,o); }
  278. virtual void write_edge_entry(ostream& o, GenPtr& x)  const { Print(x,o); }
  279.  
  280. virtual void print_node_entry(ostream&, GenPtr&)  const {}
  281. virtual void print_edge_entry(ostream&, GenPtr&)  const {}
  282.  
  283. virtual char* node_type()  const { return "void"; }
  284. virtual char* edge_type()  const { return "void"; }
  285.  
  286. protected:
  287.  
  288. graph* parent;           // for subgraphs
  289.  
  290.  
  291. void copy_all_entries() const;
  292. void clear_all_entries() const;
  293.  
  294. public:
  295.  
  296. virtual int cmp_node_entry(node, node) const { return 0; }
  297. virtual int cmp_edge_entry(edge, edge) const { return 0; }
  298.  
  299.    int adj_edges_select() { return undirected ? 1 : 0; }
  300.  
  301.    int  space() const;
  302.    void reset() const;
  303.  
  304.  
  305.    int  indeg(node v)     const;
  306.    int  outdeg(node v)    const;
  307.    int  degree(node v)    const;
  308.    node source(edge e)    const;
  309.    node target(edge e)    const;
  310.    node opposite(node v, edge e) const;
  311.  
  312.    graph* super()        const;
  313.  
  314.    int max_i(node)       const;
  315.    int max_i(edge)       const;
  316.    int max_node_index()  const;
  317.    int max_edge_index()  const;
  318.  
  319.    int  number_of_nodes() const;
  320.    int  number_of_edges() const;
  321.  
  322.    list<edge> all_edges()     const;
  323.    list<node> all_nodes()     const;
  324.    list<edge> adj_edges(node) const;
  325.    list<node> adj_nodes(node) const;
  326.  
  327.    GenPtr& entry(node v);
  328.    GenPtr& entry(edge e);
  329.    GenPtr  inf(node v) const;
  330.    GenPtr  inf(edge e) const;
  331.  
  332. int int_inf(edge e) const { return int(e->data[0]); }
  333.  
  334.  
  335.    void init_adj_iterator(node v)        const;
  336.    bool next_adj_edge(edge& e,node v)    const;
  337.    bool current_adj_edge(edge& e,node v) const;
  338.    bool next_adj_node(node& w,node v)    const;
  339.    bool current_adj_node(node& w,node v) const;
  340.  
  341.    void init_node_iterator() const {}
  342.    void init_edge_iterator() const {}
  343.    
  344.    node first_node()      const;
  345.    node last_node()       const;
  346.    node choose_node()     const;
  347.    node succ_node(node v) const;
  348.    node pred_node(node v) const;
  349.  
  350.    edge first_edge()      const;
  351.    edge last_edge()       const;
  352.    edge choose_edge()     const;
  353.    edge succ_edge(edge e) const;
  354.    edge pred_edge(edge e) const;
  355.  
  356.    edge first_adj_edge(node v) const;
  357.    edge last_adj_edge(node v)  const;
  358.    edge adj_succ(edge e)  const;
  359.    edge adj_pred(edge e)  const;
  360.    edge cyclic_adj_succ(edge e) const;
  361.    edge cyclic_adj_pred(edge e) const;
  362.  
  363.    edge first_in_edge(node v)  const;
  364.    edge last_in_edge(node v)   const;
  365.    edge in_succ(edge e)  const;
  366.    edge in_pred(edge e)  const;
  367.    edge cyclic_in_succ(edge e) const;
  368.    edge cyclic_in_pred(edge e) const;
  369.  
  370. protected:
  371.  
  372.    node new_node(GenPtr);
  373.    edge new_edge(node, node, GenPtr);
  374.    edge new_edge(edge, node, GenPtr, int dir=0);
  375.    edge new_edge(edge, edge, GenPtr, int dir1=0, int dir2=0);
  376.  
  377.    void assign(node v,GenPtr x);
  378.    void assign(edge e,GenPtr x);
  379.  
  380. public:
  381.  
  382.    node new_node()   { GenPtr x; init_node_entry(x);  
  383.                        return new_node(x); }
  384.  
  385.    edge new_edge(node v, node w) 
  386.    { GenPtr x; init_edge_entry(x);
  387.      return new_edge(v,w,x);}
  388.  
  389.    edge new_edge(edge e, node w, int dir=0) 
  390.    { GenPtr x; init_edge_entry(x);
  391.      return new_edge(e,w,x,dir); }
  392.  
  393.    edge new_edge(edge e1, edge e2, int dir1=0, int dir2=0) 
  394.    { GenPtr x; init_edge_entry(x);
  395.      return new_edge(e1,e2,x,dir1,dir2); }
  396.  
  397.    void hide_edge(edge);
  398.    void restore_edge(edge);
  399.  
  400.    void del_node(node);
  401.    void del_edge(edge);
  402.    void del_all_nodes(); 
  403.    void del_all_edges(); 
  404.  
  405.    list<edge> insert_reverse_edges();
  406.  
  407.    void sort_nodes(cmp_graph_node);
  408.    void sort_edges(cmp_graph_edge);
  409.  
  410.    void sort_nodes(const graph_array<node>&);
  411.    void sort_edges(const graph_array<edge>&);
  412.  
  413.    void sort_edges();
  414.    void sort_nodes();
  415.  
  416.    edge rev_edge(edge);
  417.    graph& rev();
  418.  
  419.    void make_undirected() { undirected = true; }
  420.    void make_directed()   { undirected = false; }
  421.  
  422.    void write(ostream& = cout) const;
  423.    void write(string) const;
  424.  
  425.    int  read(istream& = cin);
  426.    int  read(string);
  427.  
  428.    void print_node(node,ostream& = cout)  const;
  429.  
  430. virtual void print_edge(edge,ostream& = cout) const;
  431.  
  432.    void print(string s, ostream& = cout) const;
  433.  
  434.    void print()           const { print("");   }
  435.    void print(ostream& o) const { print("",o); }
  436.  
  437. virtual void clear();
  438.  
  439.    graph();
  440.    graph(const graph&);
  441.    graph& operator=(const graph&); 
  442.  
  443. virtual ~graph(){ clear(); }
  444.  
  445.  
  446.    //subgraph constructors
  447.  
  448.    graph(graph&, const list<node>&, const list<edge>&);
  449.    graph(graph&, const list<edge>&);
  450.  
  451. };
  452.  
  453. inline int  graph::outdeg(node v) const { return v->adj_edges[0].length(); }
  454. inline int  graph::indeg(node v)  const { return v->adj_edges[1].length(); }
  455. inline int  graph::degree(node v) const { return outdeg(v) + indeg(v); }
  456.  
  457. inline node graph::source(edge e)    const   { return e->s; }
  458. inline node graph::target(edge e)    const   { return e->t; }
  459. inline node graph::opposite(node v,edge e) const {return (v==e->s)?e->t:e->s;}
  460.  
  461. inline graph* graph::super()       const   { return parent; }
  462. inline int graph::max_i(node)      const   { return max_n_index; }
  463. inline int graph::max_i(edge)      const   { return max_e_index; }
  464. inline int graph::max_node_index() const   { return max_n_index; }
  465. inline int graph::max_edge_index() const   { return max_e_index; }
  466.  
  467. inline int  graph::number_of_nodes() const   { return V.length(); }
  468. inline int  graph::number_of_edges() const   { return E.length(); }
  469.  
  470. inline GenPtr& graph::entry(node v)        { return v->data[0]; }
  471. inline GenPtr& graph::entry(edge e)        { return e->data[0]; }
  472. inline void graph::assign(node v,GenPtr x) { v->data[0] = x; }
  473. inline void graph::assign(edge e,GenPtr x) { e->data[0] = x; }
  474.  
  475. inline GenPtr  graph::inf(node v) const { return v->data[0]; }
  476. inline GenPtr  graph::inf(edge e) const { return e->data[0]; }
  477.  
  478.  
  479. inline node graph::first_node()   const { return node(node_link(V.first())); }
  480. inline node graph::last_node()    const { return node(node_link(V.last())); }
  481. inline node graph::choose_node()  const { return first_node(); }
  482.  
  483. inline node graph::succ_node(node v)  const  
  484. { return node(node_link(V.succ(node_link(v)))); }
  485.  
  486. inline node graph::pred_node(node v)  const  
  487. { return node(node_link(E.pred(node_link(v)))); }
  488.  
  489.  
  490. inline edge graph::first_edge()   const { return edge(edge_link(E.first())); }
  491. inline edge graph::last_edge()    const { return edge(edge_link(E.last())); }
  492. inline edge graph::choose_edge()  const { return first_edge(); }
  493.  
  494. inline edge graph::succ_edge(edge e)  const  
  495. { return edge(edge_link(E.succ(edge_link(e)))); }
  496.  
  497. inline edge graph::pred_edge(edge e)  const  
  498. { return edge(edge_link(E.pred(edge_link(e)))); }
  499.  
  500.  
  501.  
  502. inline edge graph::first_adj_edge(node v) const
  503. { return edge(adj_link1(v->adj_edges[0].first())); }
  504.  
  505. inline edge graph::last_adj_edge(node v)  const
  506. { return edge(adj_link1(v->adj_edges[0].last())); }
  507.  
  508. inline edge graph::adj_succ(edge e)  const
  509. { return edge(adj_link1(adj_link1(e)->succ_item())); }
  510.  
  511. inline edge graph::adj_pred(edge e)  const
  512. { return edge(adj_link1(adj_link1(e)->pred_item())); }
  513.  
  514. inline edge graph::cyclic_adj_succ(edge e) const 
  515. { edge e1 = adj_succ(e);
  516.   return e1 ? e1 : first_adj_edge(e->s); }
  517.  
  518. inline edge graph::cyclic_adj_pred(edge e) const 
  519. { edge e1 = adj_pred(e);
  520.   return e1 ? e1 : last_adj_edge(e->s); }
  521.  
  522.  
  523.  
  524. inline edge graph::first_in_edge(node v) const
  525. { return edge(adj_link2(v->adj_edges[1].first())); }
  526.  
  527. inline edge graph::last_in_edge(node v)  const
  528. { return edge(adj_link2(v->adj_edges[1].last())); }
  529.  
  530. inline edge graph::in_succ(edge e)  const
  531. { return edge(adj_link2(adj_link2(e)->succ_item())); }
  532.  
  533. inline edge graph::in_pred(edge e)  const
  534. { return edge(adj_link2(adj_link2(e)->pred_item())); }
  535.  
  536. inline edge graph::cyclic_in_succ(edge e) const 
  537. { edge e1 = in_succ(e);
  538.   return e1 ? e1 : first_in_edge(e->s); }
  539.  
  540. inline edge graph::cyclic_in_pred(edge e) const 
  541. { edge e1 = in_pred(e);
  542.   return e1 ? e1 : last_in_edge(e->s); }
  543.  
  544.  
  545.  
  546. inline void graph::init_adj_iterator(node v) const 
  547. { v->adj_iterator = nil; }
  548.  
  549. inline bool  graph::current_adj_edge(edge& e,node v) const 
  550. { return (e = v->adj_iterator) != nil;}
  551.  
  552. inline bool  graph::next_adj_edge(edge& e,node v) const 
  553. { if (v->adj_iterator) 
  554.       e = v->adj_iterator = adj_succ(v->adj_iterator);
  555.   else
  556.       e = v->adj_iterator = first_adj_edge(v);
  557.   return  (e) ? true : false;
  558.  }
  559.  
  560. inline bool graph::next_adj_node(node& w,node v)  const
  561. { edge e;
  562.   if (next_adj_edge(e,v))
  563.   { //w = (v==e->s) ? e->t : e->s;  // ugraph
  564.     w = e->t;
  565.     return true; 
  566.    }
  567.   else return false;
  568.  }
  569.    
  570. inline bool graph::current_adj_node(node& w,node v)  const
  571. { edge e;
  572.   if (current_adj_edge(e,v))
  573.   { //w = (v==e->s) ? e->t : e->s;  // ugraph
  574.     w = e->t;
  575.     return true; 
  576.    }
  577.   else return false;
  578. }
  579.    
  580.  
  581. //------------------------------------------------------------------------------
  582. // Iteration   (macros)
  583. //------------------------------------------------------------------------------
  584.  
  585. #define forall_nodes(v,g) for (v=(g).first_node(); v; v=(g).succ_node(v) )
  586. #define forall_edges(e,g) for (e=(g).first_edge(); e; e=(g).succ_edge(e) )
  587.  
  588. #define Forall_nodes(v,g) for (v=(g).last_node(); v; v=(g).pred_node(v) )
  589. #define Forall_edges(e,g) for (e=(g).last_edge(); e; e=(g).pred_edge(e) )
  590.  
  591.  
  592. #define forall_out_edges(e,v)\
  593. for(e = First_Adj_Edge(v,0); e != Leda_Nil_Edge(0); e = Succ_Adj_Edge(e,0))
  594.  
  595. #define forall_in_edges(e,v)\
  596. for(e = First_Adj_Edge(v,1); e != Leda_Nil_Edge(1); e = Succ_Adj_Edge(e,1))
  597.  
  598. #define ADJ_BREAK { adj_loop_index = -1; break; }
  599.  
  600. #define forall_inout_edges(e,v)\
  601. for(LEDA::loop_dummy = 0; LEDA::loop_dummy < 1; LEDA::loop_dummy++)\
  602. for(int adj_loop_index = 1; adj_loop_index>=0; adj_loop_index--)\
  603. for(e = First_Adj_Edge(v,adj_loop_index);\
  604. e != Leda_Nil_Edge(adj_loop_index);\
  605. e = Succ_Adj_Edge(e,adj_loop_index))
  606.  
  607. #define forall_adj_edges(e,v)\
  608. for(LEDA::loop_dummy = 0; LEDA::loop_dummy < 1; LEDA::loop_dummy++)\
  609. for(int adj_loop_index = graph_of(v)->adj_edges_select(); adj_loop_index>=0; adj_loop_index--)\
  610. for(e = First_Adj_Edge(v,adj_loop_index);\
  611. e != Leda_Nil_Edge(adj_loop_index);\
  612. e = Succ_Adj_Edge(e,adj_loop_index))
  613.  
  614. #define forall_adj_nodes(u,v)\
  615. for(LEDA::loop_dummy = 0; LEDA::loop_dummy < 1; LEDA::loop_dummy++)\
  616. for(int adj_loop_index = graph_of(v)->adj_edges_select(); adj_loop_index>=0; adj_loop_index--)\
  617. for(edge adj_loop_e = First_Adj_Edge(v,adj_loop_index);\
  618. (adj_loop_e!=Leda_Nil_Edge(adj_loop_index))&&((u=opposite(v,adj_loop_e))||1);\
  619. adj_loop_e = Succ_Adj_Edge(adj_loop_e,adj_loop_index))
  620.  
  621.  
  622.  
  623.  
  624. //------------------------------------------------------------------------------
  625. // GRAPH<vtype,etype> : parameterized directed graphs
  626. //------------------------------------------------------------------------------
  627.  
  628.  
  629. template<class vtype, class etype> 
  630.  
  631. class _CLASSTYPE GRAPH : public graph {
  632.  
  633. vtype X;
  634. etype Y;
  635.  
  636. void copy_node_entry(GenPtr& x) const  { x=Copy(ACCESS(vtype,x)); }
  637. void copy_edge_entry(GenPtr& x) const  { x=Copy(ACCESS(etype,x)); }
  638.  
  639. void clear_node_entry(GenPtr& x) const { Clear(ACCESS(vtype,x)); }
  640. void clear_edge_entry(GenPtr& x) const { Clear(ACCESS(etype,x)); }
  641.  
  642. void write_node_entry(ostream& o, GenPtr& x) const {Print(ACCESS(vtype,x),o);}
  643. void write_edge_entry(ostream& o, GenPtr& x) const {Print(ACCESS(etype,x),o);}
  644.  
  645. void read_node_entry(istream& i, GenPtr& x) { Read(X,i); x=Copy(X); }
  646. void read_edge_entry(istream& i, GenPtr& x) { Read(Y,i); x=Copy(Y); }
  647.  
  648. void init_node_entry(GenPtr& x) { Init(X); x = Copy(X); }
  649. void init_edge_entry(GenPtr& x) { Init(Y); x = Copy(Y); }
  650.  
  651. void print_node_entry(ostream& o, GenPtr& x)  const
  652.      { o << "("; Print(ACCESS(vtype,x),o); o << ")"; }
  653. void print_edge_entry(ostream& o, GenPtr& x)  const
  654.      { o << "("; Print(ACCESS(etype,x),o); o << ")"; }
  655.  
  656. char* node_type()  const { return TYPE_NAME(vtype); }
  657. char* edge_type()  const { return TYPE_NAME(etype); }
  658.  
  659. public:
  660.  
  661. int cmp_node_entry(node x, node y) const { return compare(inf(x),inf(y)); }
  662. int cmp_edge_entry(edge x, edge y) const { return compare(inf(x),inf(y)); }
  663.  
  664. vtype  inf(node v)    const   { return ACCESS(vtype,graph::inf(v)); }
  665. etype  inf(edge e)    const   { return ACCESS(etype,graph::inf(e)); }
  666.  
  667. vtype& operator[] (node v)    { return ACCESS(vtype,entry(v)); }
  668. etype& operator[] (edge e)    { return ACCESS(etype,entry(e)); }
  669. vtype  operator[] (node v) const   { return ACCESS(vtype,graph::inf(v)); }
  670. etype  operator[] (edge e) const   { return ACCESS(etype,graph::inf(e)); }
  671.  
  672. void   assign(node v,vtype x) { operator[](v) = x; }
  673. void   assign(edge e,etype x) { operator[](e) = x; }
  674.  
  675. node   new_node()               { return graph::new_node(); }
  676. node   new_node(vtype a)        { return graph::new_node(Copy(a)); }
  677.  
  678. edge   new_edge(node v, node w) { return graph::new_edge(v,w); }
  679. edge   new_edge(node v, node w, etype a)
  680.                                 { return graph::new_edge(v,w,Copy(a)); }
  681. edge   new_edge(edge e, node w) { return graph::new_edge(e,w); }
  682. edge   new_edge(edge e, node w, etype a)
  683.                                 { return graph::new_edge(e,w,Copy(a),0); }
  684. edge   new_edge(edge e, node w, etype a, int dir)
  685.                                 { return graph::new_edge(e,w,Copy(a),dir); }
  686.  
  687. void   clear()                  { clear_all_entries(); graph::clear(); }
  688.  
  689. GRAPH<vtype,etype>& operator=(const GRAPH<vtype,etype>& a)
  690. { clear_all_entries();graph::operator=(a);copy_all_entries();return *this; }
  691.  
  692. GRAPH()  {}
  693. GRAPH(const GRAPH<vtype,etype>& a) : graph(a) { a.copy_all_entries(); } 
  694.  
  695. /* subgraphs */
  696. GRAPH(GRAPH<vtype,etype>& a, const list<node>& b, const list<edge>& c) 
  697.                                                   : graph(a,b,c) {}
  698.  
  699. GRAPH(GRAPH<vtype,etype>& a, const list<edge>& c) : graph(a,c) {}
  700.  
  701. virtual ~GRAPH()   { if (parent==0) clear_all_entries(); }
  702.  
  703. };
  704.  
  705.  
  706. //------------------------------------------------------------------------------
  707. // node_list
  708. //------------------------------------------------------------------------------
  709.  
  710. class node_list : public c_obj_list
  711. {
  712.   node iterator;
  713.  
  714. public:
  715.  
  716.   static void del_node(node v) { aux_link(v)->del_item(); }
  717.  
  718.   void append(node v) { c_obj_list::append(aux_link(v)); }
  719.   void push(node v)   { c_obj_list::push(aux_link(v)); }
  720.   void insert(node v, node w) 
  721.                       { c_obj_list::insert(aux_link(v),aux_link(w)); }
  722.   node pop()          { return node(aux_link(c_obj_list::pop())); }
  723.   void del(node v)    { c_obj_list::del(aux_link(v)); }
  724.  
  725.   bool member(node v)  const { return aux_link(v)->succ_link != nil; }
  726.   bool operator()(node v) const { return member(v); }
  727.  
  728.   node first()const { return node(aux_link(c_obj_list::first())); }
  729.   node last() const { return node(aux_link(c_obj_list::last()));  }
  730.   node head() const { return node(aux_link(c_obj_list::first())); }
  731.   node tail() const { return node(aux_link(c_obj_list::last()));  }
  732.  
  733.   node succ(node v) const
  734.   { return node(aux_link(c_obj_list::succ(aux_link(v)))); }
  735.  
  736.   node pred(node v) const
  737.   { return node(aux_link(c_obj_list::pred(aux_link(v)))); }
  738.  
  739.   node cyclic_succ(node v) const
  740.   { return node(aux_link(c_obj_list::cyclic_succ(aux_link(v)))); }
  741.  
  742.   node cyclic_pred(node v) const
  743.   { return node(aux_link(c_obj_list::cyclic_pred(aux_link(v)))); }
  744.  
  745.   void start_iteration() const { (*(node*)&iterator)=first(); }
  746.   void move_to_succ() const { (*(node*)&iterator) = succ(iterator);}
  747.  
  748.   bool read_iterator(node& x) const { x = iterator; return x ? true : false; }
  749.  
  750.   node first_item() const { return first(); }
  751.   node last_item()  const { return last(); }
  752.  
  753.   GenPtr forall_loop_test(GenPtr x, node& v) const { return v = node(x); }
  754.  
  755.   void   loop_to_succ(GenPtr& x) const { x = succ(node(x)); }
  756.   void   loop_to_pred(GenPtr& x) const { x = pred(node(x)); }
  757.  
  758. };
  759.  
  760.  
  761.  
  762. //------------------------------------------------------------------------------
  763. // node_stack 
  764. //------------------------------------------------------------------------------
  765.  
  766. class node_stack {
  767.  
  768. node head;
  769.  
  770. public:
  771.  
  772. node_stack() { head = nil; }
  773.  
  774. void push(node v) { v->data[1] = head; head = v; }
  775. node pop()        { node v = head; head = node(v->data[1]); return v; }
  776. bool empty()      { return (head==nil) ? true : false; }  
  777. void clear()      { head = nil; }  
  778.  
  779. };
  780.  
  781.  
  782. //------------------------------------------------------------------------------
  783. // node_queue 
  784. //------------------------------------------------------------------------------
  785.  
  786. class node_queue {
  787.  
  788. node head;
  789. node tail;
  790.  
  791. public:
  792.  
  793. node_queue() { head = nil; }
  794.  
  795. void append(node v) 
  796. { v->data[1] = nil; 
  797.   if (head == nil) 
  798.      head = v;
  799.   else
  800.      tail->data[1] = v; 
  801.   tail = v; 
  802.  }
  803.  
  804. node pop()   { node v = head; head = node(v->data[1]); return v; }
  805. bool empty() { return (head==nil) ? true : false; }  
  806. void clear() { head = nil; }  
  807.  
  808. };
  809.  
  810.  
  811.  
  812.  
  813. //------------------------------------------------------------------------------
  814. // node_data 
  815. //------------------------------------------------------------------------------
  816.  
  817.  
  818. template <class T> class node_data {
  819.  
  820. public:
  821.  
  822. T& operator[](node v) { return (T&)v->data[2]; }
  823. T  operator()(node v) { return (T)v->data[2]; }
  824.  
  825. T    get(node v) { return (T)v->data[2]; }
  826. void set(node v,T x) { v->data[2] = GenPtr(x); }
  827.  
  828. node_data(const graph& G, T x) { init_node_data(G,2,GenPtr(x)); }
  829.  
  830. };
  831.  
  832.  
  833.  
  834. //------------------------------------------------------------------------------
  835. // node and edge arrays
  836. //------------------------------------------------------------------------------
  837.  
  838.  
  839. #if defined(LEDA_CHECKING_OFF)
  840. #define GRAPH_ARRAY_ACCESS(I,type)\
  841. type& operator[](I x)       { return ACCESS(type,arr[index(x)]); }\
  842. type  operator[](I x) const { return ACCESS(type,arr[index(x)]); }
  843. #else
  844. #define GRAPH_ARRAY_ACCESS(I,type)\
  845. type& operator[](I x)       { return ACCESS(type,entry(x));}\
  846. type  operator[](I x) const { return ACCESS(type,inf(x));}
  847. #endif
  848.  
  849.  
  850. //------------------------------------------------------------------------------
  851. // node arrays
  852. //------------------------------------------------------------------------------
  853.  
  854.  
  855. typedef graph_array<node>  node_graph_array;
  856.  
  857.  
  858. template<class type>
  859.  
  860. class _CLASSTYPE node_array : public node_graph_array {
  861.  
  862. type X;
  863.  
  864. void copy_entry(GenPtr& x) const { x=Copy(ACCESS(type,x));}
  865. void clear_entry(GenPtr& x)const { Clear(ACCESS(type,x)); }
  866.  
  867. public:
  868.  
  869.  
  870. int cmp_entry(node x,node y) const 
  871. { return compare(ACCESS(type,arr[index(x)]),ACCESS(type,arr[index(y)])); }
  872.  
  873. GRAPH_ARRAY_ACCESS(node,type)
  874.  
  875. type& elem(int i)              { return ACCESS(type,arr[i]);}
  876. type  elem(int i) const        { return ACCESS(type,arr[i]);}
  877.  
  878.  
  879.  
  880. void init(const graph& G, int n, type i) { node_graph_array::init(G,n,Convert(i)); }
  881.  
  882. #if defined(__ZTC__)
  883. void init(const graph& G);
  884. #else
  885. void init(const graph& G) { Init(X); init(G,X); }
  886. #endif
  887.  
  888. void init(const graph& G, type i)    { init(G,G.max_i(node(0))+1,i); }
  889. void init(const node_array<type>& A) { node_graph_array::init(A); }
  890.  
  891.  
  892. node_array() {}
  893. node_array(const graph& G)                 { init(G);   }
  894. node_array(const graph& G, int n, type i)  { init(G,n,i); }
  895. node_array(const graph& G, type i)         { init(G,i); }
  896. node_array(const node_array<type>& A)      { init(A);   }
  897.  
  898. node_array<type>& operator=(const node_array<type>& A) { init(A); return *this;}
  899.  
  900. ~node_array() { node_graph_array::clear(); }
  901.  
  902. };
  903.  
  904. #if defined (__ZTC__)
  905. template<class type>
  906. inline void  node_array<type>::init(const graph& G)  { Init(X); init(G,X); }
  907. #endif
  908.  
  909.  
  910.  
  911. /*
  912.  
  913. template<class type>
  914.  
  915. class _CLASSTYPE node_array1 {
  916.  
  917. graph* g;
  918. int sz; 
  919. type* arr;
  920.  
  921.  
  922. public:
  923.  
  924. #if defined(LEDA_CHECKING_OFF)
  925. type& operator[](node x)       { return arr[index(x)]; }
  926. type  operator[](node x) const { return arr[index(x)]; }
  927. #else
  928. type& operator[](node x)
  929.  { if (g != graph_of(x) || index(x) >= sz)
  930.           error_handler(102,"(node/edge)_array[x]: not defined for x");
  931.   return arr[index(x)];
  932.  }
  933.  type  operator[](node x) const
  934.  { if (g != graph_of(x) || index(x) >= sz)
  935.           error_handler(102,"(node/edge)_array[x]: not defined for x");
  936.   return arr[index(x)];
  937.  }
  938. #endif
  939.  
  940.  
  941.  
  942. void init(const graph& G, int n, type ini)
  943. { g = (graph*)&G;  
  944.   sz = n; 
  945.   arr = new type[sz];
  946.   for(int i = 0; i<sz; i++) arr[i] = ini;
  947.  }
  948.  
  949. void init(const graph& G, type ini)
  950. { g = (graph*)&G;  
  951.   sz = G.max_i(node(0))+1; 
  952.   arr = new type[sz];
  953.   for(int i = 0; i<sz; i++) arr[i] = ini;
  954. }
  955.  
  956. void init(const graph& G)
  957. { g = (graph*)&G;  
  958.   sz = G.max_i(node(0))+1; 
  959.   arr = new type[sz];
  960. }
  961.  
  962.  
  963. void init(const node_array1<type>& A) 
  964. { g = A.g;
  965.   sz = A.sz;
  966.   arr = new type[sz];
  967.   for(int i = 0; i<sz; i++) arr[i] = A.arr[i];
  968. }
  969.  
  970.  
  971. node_array1() {}
  972. node_array1(const graph& G)                 { init(G);   }
  973. //node_array1(const graph& G, int n)        { init(G,n); }
  974. node_array1(const graph& G, int n, type i)  { init(G,n,i); }
  975. node_array1(const graph& G, type i)         { init(G,i); }
  976. node_array1(const node_array1<type>& A)     { init(A);   }
  977. node_array1<type>& operator=(const node_array1<type>& A) 
  978. { init(A); return *this; }
  979.  
  980. ~node_array1() { delete[] arr; }
  981.  
  982. };
  983. */
  984.  
  985.  
  986. //------------------------------------------------------------------------------
  987. // edge arrays
  988. //------------------------------------------------------------------------------
  989.  
  990. typedef graph_array<edge>  edge_graph_array;
  991.  
  992.  
  993. template<class type>
  994.  
  995. class _CLASSTYPE edge_array : public edge_graph_array {
  996.  
  997. type X;
  998.  
  999. void copy_entry(GenPtr& x) const { x=Copy(ACCESS(type,x));}
  1000. void clear_entry(GenPtr& x)const { Clear(ACCESS(type,x)); }
  1001.  
  1002. public:
  1003.  
  1004. int cmp_entry(edge x,edge y) const 
  1005. { return compare(ACCESS(type,arr[index(x)]),ACCESS(type,arr[index(y)])); }
  1006.  
  1007. GRAPH_ARRAY_ACCESS(edge,type)
  1008.  
  1009. type& elem(int i)              { return ACCESS(type,arr[i]);}
  1010. type  elem(int i) const        { return ACCESS(type,arr[i]);}
  1011.  
  1012.  
  1013. void init(const graph& G, int n, type i) { edge_graph_array::init(G,n,Convert(i)); }
  1014.  
  1015. #if defined(__ZTC__)
  1016. void init(const graph& G);
  1017. #else
  1018. void init(const graph& G) { Init(X); init(G,X); }
  1019. #endif
  1020.  
  1021. void init(const graph& G, type i)        { init(G,G.max_i(edge(0))+1,i); }
  1022. void init(const edge_array<type>& A)     { edge_graph_array::init(A); }
  1023.  
  1024. edge_array() {}
  1025. edge_array(const graph& G)                 { init(G);   }
  1026. edge_array(const graph& G, int n, type i)  { init(G,n,i); }
  1027. edge_array(const graph& G, type i)         { init(G,i); }
  1028. edge_array(const edge_array<type>& A)      { init(A);   }
  1029.  
  1030. edge_array<type>& operator=(const edge_array<type>& A) { init(A); return *this;}
  1031.  
  1032. ~edge_array() { edge_graph_array::clear(); }
  1033.  
  1034. };
  1035.  
  1036. #if defined(__ZTC__)
  1037. template<class type>
  1038. inline void  edge_array<type>::init(const graph& G)  { Init(X); init(G,X); }
  1039. #endif
  1040.  
  1041.  
  1042.  
  1043.  
  1044.  
  1045. //-----------------------------------------------------------------------------
  1046. // graph generators
  1047. //-----------------------------------------------------------------------------
  1048.  
  1049. extern void complete_graph(graph&,int);
  1050. extern void random_graph(graph&,int,int);
  1051. extern void test_graph(graph&);
  1052.  
  1053. extern void complete_bigraph(graph&,int,int,list<node>&,list<node>&);
  1054. extern void random_bigraph(graph&,int,int,int,list<node>&,list<node>&);
  1055. extern void test_bigraph(graph&,list<node>&,list<node>&);
  1056.  
  1057.  
  1058. extern void random_planar_graph(graph&,node_array<double>& xcoord, 
  1059.                                        node_array<double>& ycoord, int n);
  1060. extern void random_planar_graph(graph&,int);
  1061.  
  1062.  
  1063. extern void triangulated_planar_graph(graph&,node_array<double>& xcoord, 
  1064.                                              node_array<double>& ycoord, int n);
  1065. extern void triangulated_planar_graph(graph& G, int n);
  1066.  
  1067.  
  1068. extern void grid_graph(graph&,node_array<double>& xcoord, 
  1069.                               node_array<double>& ycoord, int n);
  1070. extern void grid_graph(graph&,int);
  1071.  
  1072.  
  1073. extern void cmdline_graph(graph&,int,char**);
  1074.  
  1075.  
  1076.  
  1077. //-----------------------------------------------------------------------------
  1078. // miscellaneous  (should be member functions ?)
  1079. //-----------------------------------------------------------------------------
  1080.  
  1081. extern bool Is_Bidirected(const graph&, edge_array<edge>&);
  1082.  
  1083. extern bool Is_Simple(graph& G);
  1084.  
  1085. extern void Make_Simple(graph& G);
  1086.  
  1087.  
  1088.  
  1089. // for historical reasons
  1090.  
  1091. inline bool compute_correspondence(const graph& G, edge_array<edge>& rev)
  1092. { return Is_Bidirected(G,rev); }
  1093.  
  1094. inline void eliminate_parallel_edges(graph& G) { Make_Simple(G); }
  1095.  
  1096.  
  1097. #endif
  1098.